package main

import "fmt"

func main() {
	fmt.Printf("order([]int{1, 6, 3, 6, 3, 4, 5, 4, 5}): %v\n", order([]int{1, 6, 3, 6, 3, 4, 5, 4, 5}))
}

type stack struct {
	n     []int
	depth int
}

func (s *stack) pop() int {
	n := s.n[s.depth-1]
	s.n = s.n[:s.depth-1]
	s.depth--
	return n
}

func (s *stack) push(num int) {
	s.n = append(s.n, num)
	s.depth++
}

func (s *stack) getDepth() int {
	return s.depth
}

func order(nums []int) []int {
	s := &stack{}
	for _, v := range nums {
		s.push(v)
	}
	fmt.Printf("s:%v\n", s.n)
	deep := s.getDepth()
	for deep > 0 {
		maxNum := getMax(s, deep)
		times := getNumTime(s, deep, maxNum)
		fmt.Printf("deep:%d, maxNum:%d,times:%d\n", deep, maxNum, times)
		Sink(s, deep, maxNum, times)
		deep -= times
	}
	return s.n
}

func getMax(s *stack, deep int) int {
	if deep == 0 {
		return -1
	}
	cur := s.pop()
	m := getMax(s, deep-1)
	s.push(cur)
	if m > cur {
		return m
	} else {
		return cur
	}
}

func getNumTime(s *stack, deep, target int) int {
	if deep == 0 {
		return 0
	}
	var time = 0
	cur := s.pop()
	time += getNumTime(s, deep-1, target)
	if cur == target {
		time++
	}
	s.push(cur)
	return time
}

func Sink(s *stack, deep, num, times int) {
	tmpS := &stack{}
	for ; deep > 0; deep-- {
		n := s.pop()
		if n != num {
			tmpS.push(n)
		}
	}
	for ; times > 0; times-- {
		s.push(num)
	}

	for tmpS.getDepth() > 0 {
		s.push(tmpS.pop())
	}
}
